/*
 * ============================================================================
 * 队列 (Queue) - C语言实现
 * ============================================================================
 * 
 * 【核心定义】
 * 队列是一种先进先出(FIFO - First In First Out)的线性数据结构。
 * 在队尾插入元素，在队头删除元素。
 * 
 * 【内存布局】
 * 数组实现（循环队列）:
 *        front           rear
 *          ↓              ↓
 *   [- | 10 | 20 | 30 | 40 | -]
 *    0   1    2    3    4   5
 * 
 * 链表实现:
 *   front → [10|next] → [20|next] → [30|next] → [40|NULL] ← rear
 * 
 * 【基本操作】
 * - enqueue(x): 将元素x加入队尾
 * - dequeue():  从队头移除元素
 * - front():    查看队头元素但不移除
 * - isEmpty():  判断队列是否为空
 * 
 * 【时间复杂度】
 * - enqueue: O(1)
 * - dequeue: O(1)
 * - front:   O(1)
 * - search:  O(n)
 * 
 * 【空间复杂度】O(n)
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

// ============================================================================
// 方式1: 循环队列（数组实现）
// ============================================================================
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;  // 队头索引
    int rear;   // 队尾索引
    int size;   // 当前元素数量
} CircularQueue;

// 创建队列
CircularQueue* createQueue() {
    CircularQueue* queue = (CircularQueue*)malloc(sizeof(CircularQueue));
    queue->front = 0;
    queue->rear = -1;
    queue->size = 0;
    return queue;
}

// 判断队列是否为空
bool isQueueEmpty(CircularQueue* queue) {
    return queue->size == 0;
}

// 判断队列是否已满
bool isQueueFull(CircularQueue* queue) {
    return queue->size == MAX_SIZE;
}

// 入队
void enqueue(CircularQueue* queue, int value) {
    if (isQueueFull(queue)) {
        printf("错误: 队列已满\n");
        return;
    }
    queue->rear = (queue->rear + 1) % MAX_SIZE;  // 循环
    queue->data[queue->rear] = value;
    queue->size++;
}

// 出队
int dequeue(CircularQueue* queue) {
    if (isQueueEmpty(queue)) {
        printf("错误: 队列为空\n");
        return -1;
    }
    int value = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAX_SIZE;  // 循环
    queue->size--;
    return value;
}

// 查看队头元素
int frontElement(CircularQueue* queue) {
    if (isQueueEmpty(queue)) {
        printf("错误: 队列为空\n");
        return -1;
    }
    return queue->data[queue->front];
}

// 获取队列大小
int queueSize(CircularQueue* queue) {
    return queue->size;
}

// 打印队列
void printQueue(CircularQueue* queue) {
    if (isQueueEmpty(queue)) {
        printf("队列为空\n");
        return;
    }
    printf("队头 → [");
    int idx = queue->front;
    for (int i = 0; i < queue->size; i++) {
        printf("%d", queue->data[idx]);
        if (i < queue->size - 1) printf(", ");
        idx = (idx + 1) % MAX_SIZE;
    }
    printf("] ← 队尾\n");
}

// ============================================================================
// 方式2: 链表队列
// ============================================================================
typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;
    QueueNode* rear;
    int count;
} LinkedQueue;

// 创建链表队列
LinkedQueue* createLinkedQueue() {
    LinkedQueue* queue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
    queue->front = NULL;
    queue->rear = NULL;
    queue->count = 0;
    return queue;
}

// 入队（链表）
void enqueueLinked(LinkedQueue* queue, int value) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->data = value;
    newNode->next = NULL;
    
    if (queue->rear == NULL) {
        queue->front = queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    queue->count++;
}

// 出队（链表）
int dequeueLinked(LinkedQueue* queue) {
    if (queue->front == NULL) {
        printf("错误: 队列为空\n");
        return -1;
    }
    QueueNode* temp = queue->front;
    int value = temp->data;
    queue->front = queue->front->next;
    
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    
    free(temp);
    queue->count--;
    return value;
}

// ============================================================================
// 应用场景1: 打印任务队列
// ============================================================================
typedef struct {
    char filename[50];
    int pages;
} PrintJob;

void example_print_queue() {
    printf("\n=== 应用场景1: 打印任务队列 ===\n");
    printf("场景: 打印机按先来后到顺序处理打印任务\n\n");
    
    CircularQueue* printQueue = createQueue();
    
    printf("添加打印任务:\n");
    enqueue(printQueue, 1);  // 文档1
    printf("  任务1: report.pdf (10页)\n");
    enqueue(printQueue, 2);  // 文档2
    printf("  任务2: invoice.pdf (3页)\n");
    enqueue(printQueue, 3);  // 文档3
    printf("  任务3: manual.pdf (50页)\n");
    
    printf("\n开始打印:\n");
    int taskNum = 1;
    while (!isQueueEmpty(printQueue)) {
        int job = dequeue(printQueue);
        printf("  正在打印任务%d...\n", job);
    }
    
    printf("\n优势: FIFO保证公平性，先提交先处理\n");
    free(printQueue);
}

// ============================================================================
// 应用场景2: 广度优先搜索(BFS)
// ============================================================================
typedef struct {
    int node;
    int level;
} BFSNode;

void example_bfs() {
    printf("\n=== 应用场景2: 广度优先搜索(BFS) ===\n");
    printf("场景: 在树或图中按层次遍历\n\n");
    
    // 模拟简单的树结构
    //       1
    //      / \\
    //     2   3
    //    / \\
    //   4   5
    
    printf("树结构:\n");
    printf("       1\n");
    printf("      / \\\\\n");
    printf("     2   3\n");
    printf("    / \\\\\n");
    printf("   4   5\n\n");
    
    LinkedQueue* bfsQueue = createLinkedQueue();
    
    printf("BFS遍历过程:\n");
    enqueueLinked(bfsQueue, 1);
    printf("  访问层0: 1\n");
    dequeueLinked(bfsQueue);
    
    enqueueLinked(bfsQueue, 2);
    enqueueLinked(bfsQueue, 3);
    printf("  访问层1: 2, 3\n");
    dequeueLinked(bfsQueue);
    dequeueLinked(bfsQueue);
    
    enqueueLinked(bfsQueue, 4);
    enqueueLinked(bfsQueue, 5);
    printf("  访问层2: 4, 5\n");
    
    printf("\n优势: 队列保证按层次顺序访问，找到最短路径\n");
    
    // 清理
    while (bfsQueue->front != NULL) {
        dequeueLinked(bfsQueue);
    }
    free(bfsQueue);
}

// ============================================================================
// 应用场景3: 操作系统进程调度
// ============================================================================
typedef struct {
    int pid;
    char name[20];
    int burst_time;
} Process;

void example_process_scheduling() {
    printf("\n=== 应用场景3: CPU进程调度(Round Robin) ===\n");
    printf("场景: 操作系统按时间片轮转调度进程\n\n");
    
    Process processes[] = {
        {1, "Browser", 10},
        {2, "Editor", 8},
        {3, "Player", 12}
    };
    
    CircularQueue* readyQueue = createQueue();
    
    printf("就绪队列中的进程:\n");
    for (int i = 0; i < 3; i++) {
        enqueue(readyQueue, i);
        printf("  PID %d: %s (执行时间: %dms)\n", 
               processes[i].pid, 
               processes[i].name, 
               processes[i].burst_time);
    }
    
    printf("\n时间片轮转调度（每次3ms）:\n");
    int time = 0;
    while (!isQueueEmpty(readyQueue)) {
        int idx = dequeue(readyQueue);
        int exec_time = (processes[idx].burst_time > 3) ? 3 : processes[idx].burst_time;
        
        printf("  时间 %d: 执行 %s (%dms)\n", time, processes[idx].name, exec_time);
        time += exec_time;
        processes[idx].burst_time -= exec_time;
        
        if (processes[idx].burst_time > 0) {
            enqueue(readyQueue, idx);  // 还没完成，重新入队
        }
    }
    
    printf("\n优势: 公平分配CPU时间，防止饥饿\n");
    free(readyQueue);
}

// ============================================================================
// 应用场景4: 消息队列
// ============================================================================
typedef struct {
    int msg_id;
    char content[50];
} Message;

void example_message_queue() {
    printf("\n=== 应用场景4: 消息队列 ===\n");
    printf("场景: 异步消息处理，生产者-消费者模式\n\n");
    
    LinkedQueue* msgQueue = createLinkedQueue();
    
    printf("生产者发送消息:\n");
    for (int i = 1; i <= 5; i++) {
        enqueueLinked(msgQueue, i);
        printf("  消息%d 已发送\n", i);
    }
    
    printf("\n消费者处理消息:\n");
    for (int i = 0; i < 3; i++) {
        int msgId = dequeueLinked(msgQueue);
        printf("  处理消息%d\n", msgId);
    }
    
    printf("\n队列中剩余 %d 条消息\n", msgQueue->count);
    printf("\n优势: 解耦生产者和消费者，缓冲流量\n");
    
    // 清理
    while (msgQueue->front != NULL) {
        dequeueLinked(msgQueue);
    }
    free(msgQueue);
}

// ============================================================================
// 主函数 - 演示所有功能
// ============================================================================
int main() {
    printf("╔════════════════════════════════════════╗\n");
    printf("║   队列 (Queue) - C语言实现             ║\n");
    printf("╚════════════════════════════════════════╝\n");
    
    // 基本操作演示
    printf("\n--- 队列基本操作（循环队列）---\n");
    CircularQueue* queue = createQueue();
    
    printf("1. 入队: 10, 20, 30, 40\n   ");
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);
    printQueue(queue);
    
    printf("2. 查看队头元素: %d\n", frontElement(queue));
    
    printf("3. 出队: %d\n", dequeue(queue));
    printf("   ");
    printQueue(queue);
    
    printf("4. 再入队: 50\n   ");
    enqueue(queue, 50);
    printQueue(queue);
    
    printf("5. 当前队列大小: %d\n", queueSize(queue));
    printf("6. 队列是否为空: %s\n", isQueueEmpty(queue) ? "是" : "否");
    
    // 链表实现演示
    printf("\n--- 队列基本操作（链表实现）---\n");
    LinkedQueue* linkedQueue = createLinkedQueue();
    enqueueLinked(linkedQueue, 100);
    enqueueLinked(linkedQueue, 200);
    enqueueLinked(linkedQueue, 300);
    printf("入队: 100, 200, 300\n");
    printf("出队: %d\n", dequeueLinked(linkedQueue));
    printf("队列大小: %d\n", linkedQueue->count);
    
    // 应用场景演示
    example_print_queue();
    example_bfs();
    example_process_scheduling();
    example_message_queue();
    
    // 优势与局限
    printf("\n╔════════════════════════════════════════╗\n");
    printf("║   优势与局限                           ║\n");
    printf("╚════════════════════════════════════════╝\n");
    printf("\n✅ 优势:\n");
    printf("  1. 所有操作都是O(1)时间复杂度\n");
    printf("  2. FIFO特性保证公平性\n");
    printf("  3. 适合流式处理和异步通信\n");
    printf("  4. 自然支持多线程场景\n");
    
    printf("\n⚠️ 局限:\n");
    printf("  1. 只能访问队头和队尾\n");
    printf("  2. 数组实现有大小限制\n");
    printf("  3. 不支持随机访问\n");
    printf("  4. 搜索效率低（需要出队）\n");
    
    printf("\n💡 最佳使用场景:\n");
    printf("  - 任务调度（打印队列、进程调度）\n");
    printf("  - 广度优先搜索(BFS)\n");
    printf("  - 消息队列、事件处理\n");
    printf("  - 缓冲区管理\n");
    printf("  - 请求处理队列\n");
    
    printf("\n📊 两种实现对比:\n");
    printf("  循环队列: 固定大小，避免假溢出，空间利用率高\n");
    printf("  链表队列: 动态大小，无上限，但有指针开销\n");
    
    // 清理
    free(queue);
    while (linkedQueue->front != NULL) {
        dequeueLinked(linkedQueue);
    }
    free(linkedQueue);
    
    return 0;
}
